#include "StdAfx.h"

#include "Ddavidlib_clustering_consensusclusteringapproach.h"

namespace Ddavidlib_clustering
{
  ConsensusClusteringInformation::ConsensusClusteringInformation()
  {
    used_consensus_clustering_approach = "LFCARSv100";
    original_clustering_direction = "";
    input_direction = "";
    output_direction = "Output\\";
    output_filename = "Clustering";
    point_number = 0;
    cluster_number_choosing_method = "AvgK";
    cluster_number_multiple = 1.0;
    cluster_number = 0;
    error_threshold = 0.0;
    core_fragment_size_threshold = 0;
    execution_times = 1;

    output_loose_fragment_clustering_result = false;
    output_loose_fragment_clustering_result_filename += "loose_fragment_clustering_result.txt";

    given_initialization = false;
    used_initialization_approach = "Random";
    given_initialization_filename = "initialization.txt";

    using_missing_mask_file = false;

    automatic_ANMI_evaluation = false;
    automatic_Rand_evaluation = false;
    automatic_VI_evaluation = false;
    ANMI_evaluation_output_filename = "ANMI.txt";
    Rand_evaluation_output_filename = "Rand.txt";
    VI_evaluation_output_filename = "VI.txt";
    evaluation_information_output_filename = "evaluation_information.txt";

    automatic_true_label_evaluation = false;
    true_label_ANMI_evaluation_output_filename = "ANMI_true_label.txt";
    true_label_Rand_evaluation_output_filename = "Rand_true_label.txt";
    true_label_VI_evaluation_output_filename = "VI_true_label.txt";
    true_label_evaluation_information_output_filename = "true_label_evaluation_information.txt";

    LFCARSv100_use_avg_similarity = false;
    
    incremental_point_number = 0;

    loose_fragment_sampling_method = "kRepresentativePointOfEachCoreFragment";
    output_loose_fragment_sampling_filename = "loose_fragment_sampling.txt";

    debug_show_round = false;
    debug_show_round_output_filename = "Round.txt";
    debug_show_fragment_number = false;
    debug_show_fragment_number_output_filename = "Fragment.txt";
    debug_show_execution_time = false;
    debug_show_execution_time_output_filename = "Time_Log.txt";
    debug_show_original_cluster_number = false;
    debug_show_original_cluster_number_output_filename = "Original_Cluster_Number.txt";
  }

  ConsensusClusteringInformation::~ConsensusClusteringInformation()
  {
  }

  Timer::Timer()
  {
    last_time = clock();
  }

  Timer::~Timer()
  {
  }

  void Timer::Reset(void)
  {
    time_counter.clear();
    last_time = clock();
  }

  void Timer::PushButton(void)
  {
    last_time = clock();
  }

  void Timer::PushButton(string event_name)
  {
    clock_t current_time;
    map<string, double>::iterator time_counter_iterator;

    current_time = clock();
    time_counter_iterator = time_counter.find(event_name);
    if(time_counter_iterator == time_counter.end())
    {
      time_counter.insert(pair<string, double>(event_name, (double)(current_time - last_time) / CLOCKS_PER_SEC));
    }
    else
    {
      time_counter_iterator->second += (double)(current_time - last_time) / CLOCKS_PER_SEC;
    }
    last_time = clock();
  }

  double Timer::OutputToFile(string filename)
  {
    ofstream output_file;
    double total_time;

    output_file.open(filename, ios::app);
    total_time = OutputToFile(output_file);
    output_file.close();

    return total_time;
  }

  double Timer::OutputToFile(ofstream &file)
  {
    map<string, double>::iterator time_counter_iterator;
    double total_time = 0.0;

    for(time_counter_iterator = time_counter.begin(); time_counter_iterator != time_counter.end(); time_counter_iterator++)
    {
      file << time_counter_iterator->first << " = " << time_counter_iterator->second << " secs" << endl;
      total_time += time_counter_iterator->second;
    }
    file << "Total time = " << total_time << " secs" << endl;

    return total_time;
  }

  ConsensusClusteringApproach::ConsensusClusteringApproach(const ConsensusClusteringInformation &consensus_clustering_information)
  {
    approach_name = "";
    point_number = consensus_clustering_information.point_number;
    cluster_number = consensus_clustering_information.cluster_number;
    original_clustering_number = 0;
    clustering_result.resize(point_number);
    max_cluster_number = 0;
    sum_cluster_number = 0;

    debug_show_original_cluster_number = consensus_clustering_information.debug_show_original_cluster_number;
    debug_show_original_cluster_number_output_filename = consensus_clustering_information.output_direction;
    debug_show_original_cluster_number_output_filename += consensus_clustering_information.debug_show_original_cluster_number_output_filename;
  }
  
  ConsensusClusteringApproach::~ConsensusClusteringApproach(void)
  {
  }

  unsigned int ConsensusClusteringApproach::GetClusterNumber(const vector<int> &input_clustering)
  {
    unsigned int point_counter;
    set<int> temp_id_list;

    for(point_counter = 0; point_counter < input_clustering.size(); ++point_counter)
    {
      if(input_clustering[point_counter] != kUnclassifiedPoint && input_clustering[point_counter] != kNoisePoint)
      {
        temp_id_list.insert(input_clustering[point_counter]);
      }
    }

    return temp_id_list.size();
  }

  unsigned int ConsensusClusteringApproach::GetMaxClusterNo(vector<int> &input_clustering)
  {
    vector<int>::iterator max_no_element;

    max_no_element = max_element(input_clustering.begin(), input_clustering.end());

    return (unsigned int)(*max_no_element);
  }

  void ConsensusClusteringApproach::GivenKRandomClusteringInitialize(vector<int> &initialized_clustering, int input_cluster_number)
  {
    unsigned int point_counter;
    unsigned int random_number;

    for(point_counter = 0; point_counter < initialized_clustering.size(); ++point_counter)
    {
      rand_s(&random_number);
      initialized_clustering[point_counter] = (int)((double)random_number / ((double)UINT_MAX + 1.0) * input_cluster_number) + 1;
      cluster_id_list.insert(initialized_clustering[point_counter]);
    }
  }

  void ConsensusClusteringApproach::MaxKRandomClusteringInitialize(vector<int> &initialized_clustering)
  {
    unsigned int point_counter;
    unsigned int random_number;
    int used_cluster_number;

    for(point_counter = 0, used_cluster_number = 0; point_counter < initialized_clustering.size(); ++point_counter)
    {
      rand_s(&random_number);
      initialized_clustering[point_counter] = (unsigned int)((double)random_number / ((double)UINT_MAX + 1.0) * max_cluster_number) + 1;
      if(initialized_clustering[point_counter] > used_cluster_number)
      {
        ++used_cluster_number;
        initialized_clustering[point_counter] = used_cluster_number;
        cluster_id_list.insert(initialized_clustering[point_counter]);
      }
    }
  }

  void ConsensusClusteringApproach::AllAloneClusteringInitialize(vector<int> &initialized_clustering)
  {
    unsigned int point_counter;

    for(point_counter = 0; point_counter < initialized_clustering.size(); ++point_counter)
    {
      initialized_clustering[point_counter] = point_counter + 1;
      cluster_id_list.insert(initialized_clustering[point_counter]);
    }
  }

  void ConsensusClusteringApproach::GivenClusteringInitialize(vector<int> &initialized_clustering, const vector<int> &input_clustering)
  {
    unsigned int point_counter;
    unsigned int random_number;

    for(point_counter = 0; point_counter < initialized_clustering.size(); ++point_counter)
    {
      initialized_clustering[point_counter] = input_clustering[point_counter];
      if(initialized_clustering[point_counter] == -1)
      {
        rand_s(&random_number);
        initialized_clustering[point_counter] = (unsigned int)((double)random_number / ((double)UINT_MAX + 1.0) * max_cluster_number) + 1;   
      }
      cluster_id_list.insert(initialized_clustering[point_counter]);
    }
  }

  double ConsensusClusteringApproach::CalculateNMIDistance(unsigned int point_number,
    vector<int> &evaluated_clustering,
    vector<int> &original_clustering)
  {
    return CalculateNMIDistance(point_number,
      evaluated_clustering, GetMaxClusterNo(evaluated_clustering),
      original_clustering, GetMaxClusterNo(original_clustering));
  }

  double ConsensusClusteringApproach::CalculateNMIDistance(unsigned int point_number,
    vector<int> &evaluated_clustering, unsigned int evaluated_clustering_cluster_number,
    vector<int> &original_clustering, unsigned int original_clustering_cluster_number)
  {
    vector<unsigned int> evaluated_clustering_cluster_size_table;
    vector<unsigned int> original_clustering_cluster_size_table;
    vector<vector<unsigned int>> intersection_counter_table;

    GetClusterSizeTable(point_number,
      evaluated_clustering, evaluated_clustering_cluster_number,
      evaluated_clustering_cluster_size_table);
    GetClusterSizeTable(point_number,
      original_clustering, original_clustering_cluster_number,
      original_clustering_cluster_size_table);

    GetIntersectionCounterTable(point_number,
      evaluated_clustering, evaluated_clustering_cluster_number,
      original_clustering, original_clustering_cluster_number,
      intersection_counter_table);

    return MI(point_number,
      evaluated_clustering_cluster_size_table, evaluated_clustering_cluster_number,
      original_clustering_cluster_size_table, original_clustering_cluster_number,
      intersection_counter_table)
      / sqrt(
      H(point_number, evaluated_clustering_cluster_size_table, evaluated_clustering_cluster_number)
      * H(point_number, original_clustering_cluster_size_table, original_clustering_cluster_number));
  }

  double ConsensusClusteringApproach::CalculateVIDistance(unsigned int point_number,
    vector<int> &evaluated_clustering,
    vector<int> &original_clustering)
  {
    return CalculateVIDistance(point_number,
      evaluated_clustering, GetMaxClusterNo(evaluated_clustering),
      original_clustering, GetMaxClusterNo(original_clustering));
  }

  double ConsensusClusteringApproach::CalculateVIDistance(unsigned int point_number,
    vector<int> &evaluated_clustering, unsigned int evaluated_clustering_cluster_number,
    vector<int> &original_clustering, unsigned int original_clustering_cluster_number)
  {
    vector<unsigned int> evaluated_clustering_cluster_size_table;
    vector<unsigned int> original_clustering_cluster_size_table;
    vector<vector<unsigned int>> intersection_counter_table;

    GetClusterSizeTable(point_number,
      evaluated_clustering, evaluated_clustering_cluster_number,
      evaluated_clustering_cluster_size_table);
    GetClusterSizeTable(point_number,
      original_clustering, original_clustering_cluster_number,
      original_clustering_cluster_size_table);

    GetIntersectionCounterTable(point_number,
      evaluated_clustering, evaluated_clustering_cluster_number,
      original_clustering, original_clustering_cluster_number,
      intersection_counter_table);

    return H(point_number, evaluated_clustering_cluster_size_table, evaluated_clustering_cluster_number)
      + H(point_number, original_clustering_cluster_size_table, original_clustering_cluster_number)
      - 2 * MI(point_number,
      evaluated_clustering_cluster_size_table, evaluated_clustering_cluster_number,
      original_clustering_cluster_size_table, original_clustering_cluster_number,
      intersection_counter_table);
  }

  double ConsensusClusteringApproach::CalculateAdjustedRandDistance(unsigned int point_number,
      vector<int> &evaluated_clustering,
      vector<int> &original_clustering)
  {
    unsigned int point_counter1, point_counter2;
    unsigned int N11 = 0, N10_N01 = 0, N00 = 0;
    int evaluated_pair;
    int original_pair;

    for(point_counter1 = 0; point_counter1 < point_number; ++point_counter1)
    {
      for(point_counter2 = point_counter1 + 1; point_counter2 < point_number; ++point_counter2)
      {
        // Nx?
        if(evaluated_clustering[point_counter1] == kUnclassifiedPoint ||
          evaluated_clustering[point_counter2] == kUnclassifiedPoint)
        {
          evaluated_pair = -3;
        }
        // N0?
        else if(evaluated_clustering[point_counter1] == kNoisePoint ||
          evaluated_clustering[point_counter2] == kNoisePoint ||
          evaluated_clustering[point_counter1] != evaluated_clustering[point_counter2])
        {
          evaluated_pair = 0;
        }
        // N1?
        else if(evaluated_clustering[point_counter1] == evaluated_clustering[point_counter2])
        {
          evaluated_pair = 1;
        }

        // N?x
        if(original_clustering[point_counter1] == kUnclassifiedPoint ||
          original_clustering[point_counter2] == kUnclassifiedPoint)
        {
          original_pair = -3;
        }
        // N?0
        else if(original_clustering[point_counter1] == kNoisePoint ||
          original_clustering[point_counter2] == kNoisePoint ||
          original_clustering[point_counter1] != original_clustering[point_counter2])
        {
          original_pair = 0;
        }
        // N?1
        else if(original_clustering[point_counter1] == original_clustering[point_counter2])
        {
          original_pair = 1;
        }

        // N11
        if(evaluated_pair + original_pair == 2)
        {
          ++N11;
        }
        // N10 or N01
        else if(evaluated_pair + original_pair == 1)
        {
          ++N10_N01;
        }
        // N00
        else if(evaluated_pair + original_pair == 0)
        {
          ++N00;
        }
        // Nx? or N?x
        else
        {
        }
      }
    }

    return (double)N10_N01 / (N11 + N10_N01 + N00);
  }

  void ConsensusClusteringApproach::UpdateClusterNumber(const vector<int> &input_clustering)
  {
    unsigned int input_clustering_number = GetClusterNumber(input_clustering);

    ++original_clustering_number;

    if(max_cluster_number < input_clustering_number)
    {
      max_cluster_number = input_clustering_number;
    }

    sum_cluster_number += input_clustering_number;

    if(debug_show_original_cluster_number)
    {
      ofstream output_file;

      output_file.open(debug_show_original_cluster_number_output_filename, ios::app);
      output_file << input_clustering_number << ", AvgK = " << (double)sum_cluster_number / original_clustering_number << endl;
      output_file.close();
    }
  }

  double ConsensusClusteringApproach::MI(unsigned int point_number,
    vector<unsigned int> &evaluated_clustering_cluster_size_table, unsigned int evaluated_clustering_cluster_number,
    vector<unsigned int> &original_clustering_cluster_size_table, unsigned int original_clustering_cluster_number,
    vector<vector<unsigned int>> &intersection_counter_table)
  {
    unsigned int evaluated_clustering_cluster_number_counter;
    unsigned int original_clustering_cluster_number_counter;
    double temp_value = 0.0;
    double evaluated_P, original_P, intersection_P;

    for(evaluated_clustering_cluster_number_counter = 1; evaluated_clustering_cluster_number_counter <= evaluated_clustering_cluster_number; ++evaluated_clustering_cluster_number_counter)
    {
      for(original_clustering_cluster_number_counter = 1; original_clustering_cluster_number_counter <= original_clustering_cluster_number; ++original_clustering_cluster_number_counter)
      {
        evaluated_P = (double)evaluated_clustering_cluster_size_table[evaluated_clustering_cluster_number_counter] / point_number;
        original_P = (double)original_clustering_cluster_size_table[original_clustering_cluster_number_counter] / point_number;
        intersection_P = (double)intersection_counter_table[evaluated_clustering_cluster_number_counter][original_clustering_cluster_number_counter] / point_number;
        if(evaluated_P != 0.0 && original_P != 0.0 && intersection_P != 0.0)
        {
          temp_value += intersection_P * LogBase(intersection_P / (evaluated_P * original_P), 2.0);
        }
      }
    }
    return temp_value;
  }

  double ConsensusClusteringApproach::H(unsigned int point_number, vector<unsigned int> &cluster_size_table, int cluster_number)
  {
    int cluster_counter;
    double temp_value = 0.0;
    double P;

    for(cluster_counter = 1; cluster_counter <= cluster_number; ++cluster_counter)
    {
      P = (double)cluster_size_table[cluster_counter] / point_number;
      if(P != 0.0)
      {
        temp_value += (-1.0) * P * LogBase(P, 2.0);
      }
    }
    return temp_value;
  }

  double ConsensusClusteringApproach::LogBase(double a, double base)
  {
    return log(a) / log(base);
  }

  void ConsensusClusteringApproach::GetClusterSizeTable(unsigned int point_number,
    vector<int> &input_clustering, unsigned int input_clustering_cluster_number,
    vector<unsigned int> &cluster_size_table)
  {
    unsigned int cluster_counter;
    unsigned int point_counter;

    cluster_size_table.resize(input_clustering_cluster_number + 1);
    for(cluster_counter = 0; cluster_counter <= input_clustering_cluster_number; ++cluster_counter)
    {
      cluster_size_table[cluster_counter] = 0;
    }
    for(point_counter = 0; point_counter < point_number; ++point_counter)
    {
      if(input_clustering[point_counter] != kUnclassifiedPoint)
      {
        cluster_size_table[input_clustering[point_counter]]++;
      }
    }
  }

  void ConsensusClusteringApproach::GetIntersectionCounterTable(unsigned int point_number,
    vector<int> &evaluated_clustering, unsigned int evaluated_clustering_cluster_number,
    vector<int> &original_clustering, unsigned int original_clustering_cluster_number,
    vector<vector<unsigned int>> &intersection_counter_table)
  {
    unsigned int evaluated_clustering_cluster_counter;
    unsigned int original_clustering_cluster_counter;
    unsigned int point_counter;

    intersection_counter_table.clear();
    for(evaluated_clustering_cluster_counter = 0; evaluated_clustering_cluster_counter <= evaluated_clustering_cluster_number; ++evaluated_clustering_cluster_counter)
    {
      vector<unsigned int> temp_counter_table;

      for(original_clustering_cluster_counter = 0; original_clustering_cluster_counter <= original_clustering_cluster_number; ++original_clustering_cluster_counter)
      {
        temp_counter_table.push_back(0);
      }
      intersection_counter_table.push_back(temp_counter_table);
    }
    for(point_counter = 0; point_counter < point_number; ++point_counter)
    {
      if(evaluated_clustering[point_counter] != kUnclassifiedPoint && original_clustering[point_counter] != kUnclassifiedPoint)
      {
        intersection_counter_table[evaluated_clustering[point_counter]][original_clustering[point_counter]]++;
      }
    }
  }

  Fragment::Fragment(void)
  {
  }

  Fragment::Fragment(vector<int> &input_belong_to_cluster_list)
  {
    belong_to_cluster_list = input_belong_to_cluster_list;
  }

  Fragment::Fragment(const Fragment &fragment)
  {
    point_list = fragment.point_list;
    belong_to_cluster_list = fragment.belong_to_cluster_list;
  }

  Fragment::~Fragment(void)
  {
  }

  void Fragment::operator=(const Fragment &fragment)
  {
    point_list = fragment.point_list;
    belong_to_cluster_list = fragment.belong_to_cluster_list;
  }

  void Fragment::AddPoint(unsigned int point)
  {
    point_list.push_back(point);
  }

  vector<Fragment> Fragment::SplitByClustering(const vector<int> &input_clustering)
  {
    vector<Fragment> split_fragment_list;
    unsigned int point_counter;
    unsigned int fragment_counter;
    unsigned int belong_to_cluster_list_size = belong_to_cluster_list.size();

    for(point_counter = 0; point_counter < point_list.size(); ++point_counter)
    {
      for(fragment_counter = 0; fragment_counter < split_fragment_list.size(); ++fragment_counter)
      {
        if(input_clustering[point_list[point_counter]] == split_fragment_list[fragment_counter].belong_to_cluster_list[belong_to_cluster_list_size])
        {
          break;
        }
      }
      if(fragment_counter == split_fragment_list.size())
      {
        Fragment temp_fragment(belong_to_cluster_list);

        temp_fragment.belong_to_cluster_list.push_back(input_clustering[point_list[point_counter]]);
        temp_fragment.point_list.push_back(point_list[point_counter]);

        split_fragment_list.push_back(temp_fragment);
      }
      else
      {
        split_fragment_list[fragment_counter].point_list.push_back(point_list[point_counter]);
      }
    }

    return split_fragment_list;
  }

  double Fragment::GetNormalDistanceToPoint(const vector<int> &target_point_belong_to_cluster_list)
  {
    unsigned int clustering_counter;
    double distance = 0.0;

    if(belong_to_cluster_list.size() == target_point_belong_to_cluster_list.size())
    {
      for(clustering_counter = 0; clustering_counter < belong_to_cluster_list.size(); ++clustering_counter)
      {
        if(belong_to_cluster_list[clustering_counter] == kUnclassifiedPoint
          || target_point_belong_to_cluster_list[clustering_counter] == kUnclassifiedPoint)
        {
          // distance += 0.0;
        }
        else if(belong_to_cluster_list[clustering_counter] == kNoisePoint
          || target_point_belong_to_cluster_list[clustering_counter] == kNoisePoint)
        {
          distance += 1.0;
        }
        else
        {
          if(belong_to_cluster_list[clustering_counter] == target_point_belong_to_cluster_list[clustering_counter])
          {
            // distance += 0.0;
          }
          else
          {
            distance += 1.0;
          }
        }
      }
      distance /= belong_to_cluster_list.size();
    }
    else
    {
      distance = -1.0; // Error
    }

    return distance;
  }

  double Fragment::GetNormalDistanceToFragment(const Fragment &target_fragment)
  {
    vector<int> temp_belong_to_cluster_list;

    temp_belong_to_cluster_list = target_fragment.belong_to_cluster_list;

    return GetNormalDistanceToPoint(temp_belong_to_cluster_list);
  }

  double Fragment::GetLFCARSSimilarityToPoint(const vector<int> &target_point_belong_to_cluster_list)
  {
    unsigned int clustering_counter;
    double similarity = 0.0;

    if(belong_to_cluster_list.size() == target_point_belong_to_cluster_list.size())
    {
      for(clustering_counter = 0; clustering_counter < belong_to_cluster_list.size(); ++clustering_counter)
      {
        if(belong_to_cluster_list[clustering_counter] == kUnclassifiedPoint
          || target_point_belong_to_cluster_list[clustering_counter] == kUnclassifiedPoint)
        {
          // similarity += 0.0;
        }
        else if(belong_to_cluster_list[clustering_counter] == kNoisePoint
          || target_point_belong_to_cluster_list[clustering_counter] == kNoisePoint)
        {
          // similarity += 0.0;
        }
        else
        {
          if(belong_to_cluster_list[clustering_counter] == target_point_belong_to_cluster_list[clustering_counter])
          {
            similarity += 1.0;
          }
          else
          {
            similarity -= 1.0;
          }
        }
      }
      similarity /= belong_to_cluster_list.size();
    }
    else
    {
      similarity = -2.0; // Error
    }

    return similarity;
  }

  double Fragment::GetLFCARSSimilarityToFragment(const Fragment &target_fragment)
  {
    vector<int> temp_belong_to_cluster_list;

    temp_belong_to_cluster_list = target_fragment.belong_to_cluster_list;

    return GetLFCARSSimilarityToPoint(temp_belong_to_cluster_list);
  }

  double Fragment::GetTotalLFCARSSimilarityToFragment(const Fragment &target_fragment)
  {
    return GetLFCARSSimilarityToFragment(target_fragment) * point_list.size() * target_fragment.point_list.size();
  }

  LooseFragment::LooseFragment(const Fragment &core)
  {
    core_fragment = core;
    error_threshold = 0.0;
    max_point_error = 0.0;
    total_size = core.point_list.size();
    non_core_fragments_total_size = 0;
  }

  LooseFragment::~LooseFragment(void)
  {
  }

  void LooseFragment::AddFragment(const Fragment &fragment)
  {
    double error;

    noncore_fragment_list.push_back(fragment);
    error = GetErrorToFragment(fragment);
    if(max_point_error < error)
    {
      max_point_error = error;
    }
    total_size += fragment.point_list.size();
    non_core_fragments_total_size += fragment.point_list.size();
  }

  void LooseFragment::RemoveFragment(unsigned int fragment_no)
  {
    total_size -= noncore_fragment_list[fragment_no].point_list.size();
    non_core_fragments_total_size -= noncore_fragment_list[fragment_no].point_list.size();
    noncore_fragment_list.erase(noncore_fragment_list.begin() + fragment_no);
    // may add updating max_error code UpdateMaxError()
  }

  void LooseFragment::UpdateMaxError(void)
  {
    unsigned int fragment_counter;
    double temp_error;

    max_point_error = 0.0;
    for(fragment_counter = 0; fragment_counter < noncore_fragment_list.size(); ++fragment_counter)
    {
      temp_error = 1.0 - core_fragment.GetLFCARSSimilarityToFragment(noncore_fragment_list[fragment_counter]);
      if(max_point_error < temp_error)
      {
        max_point_error = temp_error;
      }
    }
  }

  double LooseFragment::GetLFCARSSimilarityToFragment(const Fragment &target_fragment)
  {
    return core_fragment.GetLFCARSSimilarityToFragment(target_fragment);
  }

  double LooseFragment::GetErrorToFragment(const Fragment &target_fragment)
  {
    return 1.0 - core_fragment.GetLFCARSSimilarityToFragment(target_fragment);
  }

  double LooseFragment::GetLFCARSSimilarityToLooseFragment(const LooseFragment &target_loose_fragment)
  {
    return core_fragment.GetLFCARSSimilarityToFragment(target_loose_fragment.core_fragment);
  }
  
  double LooseFragment::GetTotalLFCARSSimilarityToLooseFragment(const LooseFragment &target_loose_fragment)
  {
    return core_fragment.GetLFCARSSimilarityToFragment(target_loose_fragment.core_fragment) * target_loose_fragment.total_size;
  }

  double LooseFragment::GetMaxErrorToLooseFragment(const LooseFragment &target_loose_fragment)
  {
    return max(max_point_error + target_loose_fragment.max_point_error,
      1.0 - GetLFCARSSimilarityToLooseFragment(target_loose_fragment));
  }

  double LooseFragment::GetTotalMaxErrorToLooseFragment(const LooseFragment &target_loose_fragment)
  {
    return GetMaxErrorToLooseFragment(target_loose_fragment) * non_core_fragments_total_size * target_loose_fragment.non_core_fragments_total_size;
  }

  LFCARSv100::LFCARSv100(const ConsensusClusteringInformation &consensus_clustering_information)
    : ConsensusClusteringApproach(consensus_clustering_information)
  {
    unsigned int point_counter;
    vector<int> temp_belong_to_cluster_list;
    Fragment temp_fragment;

    point_to_fragment_table.resize(point_number);
    for(point_counter = 0; point_counter < point_number; ++point_counter)
    {
      point_to_fragment_table[point_counter] = 0;  // assign all point to the same Fragment 0
      temp_fragment.point_list.push_back(point_counter);
    }
    fragment_list.push_back(temp_fragment);

    output_loose_fragment_clustering_result = consensus_clustering_information.output_loose_fragment_clustering_result;
    output_loose_fragment_clustering_result_filename += consensus_clustering_information.output_direction;
    output_loose_fragment_clustering_result_filename += consensus_clustering_information.output_loose_fragment_clustering_result_filename;

    given_initialization = consensus_clustering_information.given_initialization;
    used_initialization_approach = consensus_clustering_information.used_initialization_approach;
    given_initialization_filename += consensus_clustering_information.input_direction;
    given_initialization_filename += consensus_clustering_information.given_initialization_filename;

    error_threshold = consensus_clustering_information.error_threshold;
    core_fragment_size_threshold = consensus_clustering_information.core_fragment_size_threshold;
    if(core_fragment_size_threshold == 0)
    {
      core_fragment_size_threshold = point_number;
    }
    multi_execution_supporting = true;

    incremental_point_number = consensus_clustering_information.incremental_point_number;

    LFCARSv100_use_avg_similarity = consensus_clustering_information.LFCARSv100_use_avg_similarity;

    loose_fragment_sampling_method = consensus_clustering_information.loose_fragment_sampling_method;
    output_loose_fragment_sampling_filename = consensus_clustering_information.input_direction;
    output_loose_fragment_sampling_filename += consensus_clustering_information.output_loose_fragment_sampling_filename;

    debug_show_round = consensus_clustering_information.debug_show_round;
    debug_show_round_output_filename = consensus_clustering_information.output_direction;
    debug_show_round_output_filename += consensus_clustering_information.debug_show_round_output_filename;
    debug_show_fragment_number = consensus_clustering_information.debug_show_fragment_number;
    debug_show_fragment_number_output_filename = consensus_clustering_information.output_direction;
    debug_show_fragment_number_output_filename += consensus_clustering_information.debug_show_fragment_number_output_filename;
  }

  LFCARSv100::~LFCARSv100(void)
  {
  }

  void LFCARSv100::AddOriginalClustering(const vector<int> &input_clustering)
  {
    unsigned int fragment_counter;
    vector<Fragment> temp_fragment_list;
    unsigned int split_fragment_counter;

    timer.PushButton();

    // split the fragments
    for(fragment_counter = 0; fragment_counter < fragment_list.size(); ++fragment_counter)
    {
      vector<Fragment> temp_split_fragment_list = fragment_list[fragment_counter].SplitByClustering(input_clustering);

      for(split_fragment_counter = 0; split_fragment_counter < temp_split_fragment_list.size(); ++split_fragment_counter)
      {
        temp_fragment_list.push_back(temp_split_fragment_list[split_fragment_counter]);
      }
    }
    fragment_list = temp_fragment_list;

    // update original_clustering_number, sum_cluster_number and max_cluster_number
    UpdateClusterNumber(input_clustering);

    timer.PushButton("AddOriginalClustering");
  }
  
  void LFCARSv100::Initialize(void)
  {
    timer.PushButton();

    BuildPointToFragmentTable();
    BuildLooseFragmentList();

    if(given_initialization)
    {
      ifstream given_initialization_file;
      vector<int> temp_initial_clustering_result;
      int temp_value;

      given_initialization_file.open(given_initialization_filename, ios::in);
      
      for(;;)
      {
        given_initialization_file >> temp_value;
        if(given_initialization_file.eof())
        {
          break;
        }
        temp_initial_clustering_result.push_back(temp_value);
      }

      if(used_initialization_approach == "LFCARS_Core")
      {
        LFCARSCoreInitialize(loose_fragment_clustering_result, temp_initial_clustering_result);
      }
      
      given_initialization_file.close();
    }
    else
    {
      MaxKRandomClusteringInitialize(loose_fragment_clustering_result);
    }
    timer.PushButton("Initial");
  }

  void LFCARSv100::Reset(void)
  {
    timer.Reset();

    BuildLooseFragmentList();

    if(given_initialization)
    {
      ifstream given_initialization_file;
      vector<int> temp_initial_clustering_result;
      int temp_value;

      given_initialization_file.open(given_initialization_filename, ios::in);
      
      for(;;)
      {
        given_initialization_file >> temp_value;
        if(given_initialization_file.eof())
        {
          break;
        }
        temp_initial_clustering_result.push_back(temp_value);
      }

      if(used_initialization_approach == "LFCARS_Core")
      {
        LFCARSCoreInitialize(loose_fragment_clustering_result, temp_initial_clustering_result);
      }
      
      given_initialization_file.close();
    }
    else
    {
      MaxKRandomClusteringInitialize(loose_fragment_clustering_result);
    }

    timer.PushButton("Initial");
  }

  void LFCARSv100::KeepResultAndReset(void)
  {
    timer.Reset();

    timer.PushButton("Initial");
  }

  void LFCARSv100::Run(void)
  {
    unsigned int iteration_counter;
    unsigned int loose_fragment_counter;
    int most_similar_cluster;
    double current_similarity_threshold = (-1.0) * point_number;
    double next_similarity_threshold;
    double best_similarity;
    bool loose_fragment_moving_flag = true;

    timer.PushButton();

    if(debug_show_round)
    {
      unsigned int loose_fragment_counter;
      ofstream output_file;

      output_file.open(debug_show_round_output_filename, ios::out);
      for(loose_fragment_counter = 0; loose_fragment_counter < loose_fragment_clustering_result.size(); ++loose_fragment_counter)
      {
        output_file << loose_fragment_clustering_result[loose_fragment_counter] << " ";
      }
      output_file << endl;
      output_file.close();
    }

    for(iteration_counter = 1; loose_fragment_moving_flag; ++iteration_counter)
    {
      loose_fragment_moving_flag = false;

      for(loose_fragment_counter = 0; loose_fragment_counter < loose_fragment_list.size(); ++loose_fragment_counter)
      {
        next_similarity_threshold = 0.0;
        most_similar_cluster = FindMostSimilarCluster(loose_fragment_counter, best_similarity);
        
        if(abs(best_similarity - current_similarity_threshold) < 0.000001)
        {
        }
        else if(best_similarity > current_similarity_threshold)  // move this loose fragment to the cluster
        {
          loose_fragment_moving_flag = MoveLooseFragmentToCluster(loose_fragment_counter, most_similar_cluster);
          if(current_similarity_threshold < 0.0
            && next_similarity_threshold > best_similarity
            && best_similarity > current_similarity_threshold)
          {
            next_similarity_threshold = best_similarity;
          }
        }
        else if(best_similarity < current_similarity_threshold)  // create new cluster
        {
          CreateNewClusterForLooseFragment(loose_fragment_counter);
          loose_fragment_moving_flag = true;
        }
      }

      if(current_similarity_threshold < 0.0)
      {
        if(next_similarity_threshold < 0.0)
        {
          current_similarity_threshold = next_similarity_threshold;
        }
        else
        {
          current_similarity_threshold = 0.0;
        }
        if(!loose_fragment_moving_flag)
        {
          loose_fragment_moving_flag = true;
          current_similarity_threshold = 0.0;
        }
      }

      if(debug_show_round)
      {
        unsigned int loose_fragment_counter;
        ofstream output_file;

        output_file.open(debug_show_round_output_filename, ios::app);
        for(loose_fragment_counter = 0; loose_fragment_counter < loose_fragment_clustering_result.size(); ++loose_fragment_counter)
        {
          output_file << loose_fragment_clustering_result[loose_fragment_counter] << " ";
        }
        output_file << endl;
        output_file.close();
      }
    }

    TranslateLooseFragmentsToClusteringResult();

    timer.PushButton("Run");
  }

  void LFCARSv100::ExtendSize(unsigned int new_size)
  {
    if(new_size > loose_fragment_clustering_result.size())
    {
      loose_fragment_clustering_result.resize(new_size, kUnclassifiedPoint);
      point_to_fragment_table.resize(new_size, 0);
    }
  }

  void LFCARSv100::SampleFromLooseFragmentsToFile(void)
  {
    vector<unsigned int> sampling_point_list;
    unsigned int sampling_point_counter;
    unsigned int nonsampling_point_counter;
    ofstream output_file;

    if(loose_fragment_sampling_method == "RepresentativePointOfEachCoreFragment")
    {
      SampleFromLooseFragmentsMethod1(sampling_point_list);
    }
    else if(loose_fragment_sampling_method == "OneRandomPointEachCoreFragment")
    {
      SampleFromLooseFragmentsMethod2(sampling_point_list);
    }
    else
    {
      sampling_point_list.clear();
    }

    output_file.open(output_loose_fragment_sampling_filename, ios::app);
    nonsampling_point_counter = 0;
    // non-sampled points: -1
    // sampled points: self no. start from 0
    for(sampling_point_counter = 0; sampling_point_counter < sampling_point_list.size(); ++sampling_point_counter)
    {
      for(; nonsampling_point_counter < sampling_point_list[sampling_point_counter]; ++nonsampling_point_counter)
      {
        output_file << -1 << endl;
      }
      output_file << sampling_point_list[sampling_point_counter] << endl;
      ++nonsampling_point_counter;
    }
    for(; nonsampling_point_counter < point_number; ++nonsampling_point_counter)
    {
      output_file << -1 << endl;
    }
    for(; nonsampling_point_counter < incremental_point_number; ++nonsampling_point_counter)
    {
      output_file << sampling_point_counter << endl;
    }
    output_file.close();
  }

  bool LFCARSv100::CompareFragmentSize(const Fragment &fragment_1, const Fragment &fragment_2)
  {
    return fragment_1.point_list.size() > fragment_2.point_list.size();
  }

  void LFCARSv100::BuildPointToFragmentTable(void)
  {
    unsigned int fragment_counter;
    unsigned int point_counter;
    double avg_fragment_size = 0.0;
    double std_fragment_size = 0.0;

    for(fragment_counter = 0; fragment_counter < fragment_list.size(); ++fragment_counter)
    {
      for(point_counter = 0; point_counter < fragment_list[fragment_counter].point_list.size(); ++point_counter)
      {
        point_to_fragment_table[fragment_list[fragment_counter].point_list[point_counter]] = fragment_counter;
      }

      if(debug_show_fragment_number)
      {
        avg_fragment_size += fragment_list[fragment_counter].point_list.size();
        std_fragment_size += (double)(fragment_list[fragment_counter].point_list.size() * fragment_list[fragment_counter].point_list.size());
      }
    }

    if(debug_show_fragment_number)
    {
      ofstream output_file;

      avg_fragment_size /= fragment_list.size();
      std_fragment_size = sqrt(std_fragment_size / fragment_list.size() - avg_fragment_size * avg_fragment_size);
      
      output_file.open(debug_show_fragment_number_output_filename, ios::out);
      output_file << "Fragment Number      = " << fragment_list.size() << endl;
      output_file << "Avg Fragment Size    = " << avg_fragment_size << endl;
      output_file << "Std of Fragment Size = " << std_fragment_size << endl;
      output_file.close();
    }
  }

  void LFCARSv100::BuildLooseFragmentList(void)
  {
    unsigned int fragment_counter;
    unsigned int loose_fragment_counter;
    double temp_error;
    double min_error;
    unsigned int best_loose_fragment;

    loose_fragment_list.clear();
    loose_fragment_clustering_result.clear();
    sort(fragment_list.begin(), fragment_list.end(), CompareFragmentSize);

    for(fragment_counter = 0; fragment_counter < fragment_list.size(); ++fragment_counter)
    {
      min_error = 3.0;
      if(error_threshold != 0.0)
      {
        for(loose_fragment_counter = 0; loose_fragment_counter < loose_fragment_list.size(); ++loose_fragment_counter)
        {
          temp_error = loose_fragment_list[loose_fragment_counter].GetErrorToFragment(fragment_list[fragment_counter]);
          if(min_error > temp_error)
          {
            min_error = temp_error;
            best_loose_fragment = loose_fragment_counter;
          }
        }
      }

      if((fragment_list[fragment_counter].point_list.size() > core_fragment_size_threshold)
        || (min_error > error_threshold))  // create new Loose Fragment
      {
        LooseFragment temp_loose_fragment(fragment_list[fragment_counter]);

        loose_fragment_list.push_back(temp_loose_fragment);
        loose_fragment_list.back().error_threshold = error_threshold;
      }
      else  // join existing Loose Fragment
      {
        loose_fragment_list[best_loose_fragment].AddFragment(fragment_list[fragment_counter]);
      }
    }

    loose_fragment_clustering_result.resize(loose_fragment_list.size());

    if(debug_show_fragment_number)
    {
      ofstream output_file;

      output_file.open(debug_show_fragment_number_output_filename, ios::app);
      output_file << "Loose Fragment Number = " << loose_fragment_list.size() << endl;
      output_file.close();
    }
  }

  void LFCARSv100::LFCARSCoreInitialize(vector<int> &loose_fragment_clustering_result, const vector<int> &input_clustering)
  {
    unsigned int loose_fragment_counter;
    unsigned int cluster_of_core_point;
    unsigned int random_number;
    unsigned int used_cluster_number;
    map<unsigned int, unsigned int> temp_cluster_map_list;
    map<unsigned int, unsigned int>::const_iterator temp_cluster_iter;
    set<unsigned int> temp_used_cluster_list;

    used_cluster_number = 1;
    for(loose_fragment_counter = 0; loose_fragment_counter < loose_fragment_clustering_result.size(); ++loose_fragment_counter)
    {
      cluster_of_core_point = input_clustering[loose_fragment_list[loose_fragment_counter].core_fragment.point_list[0]];
      if(cluster_of_core_point == -1)
      {
        rand_s(&random_number);
        cluster_of_core_point = (unsigned int)((double)random_number / ((double)UINT_MAX + 1.0) * max_cluster_number) + 1;   
      }
      if(temp_used_cluster_list.find(cluster_of_core_point) == temp_used_cluster_list.end())
      {
        temp_used_cluster_list.insert(cluster_of_core_point);
        temp_cluster_map_list.insert(pair<unsigned int, unsigned int>(cluster_of_core_point, used_cluster_number));
        if(max_cluster_number < used_cluster_number)
        {
          max_cluster_number = used_cluster_number;
        }
        ++used_cluster_number;
      }
      temp_cluster_iter = temp_cluster_map_list.find(cluster_of_core_point);
      loose_fragment_clustering_result[loose_fragment_counter] = temp_cluster_iter->second;
      cluster_id_list.insert(loose_fragment_clustering_result[loose_fragment_counter]);
    }
  }

  unsigned int LFCARSv100::FindMostSimilarCluster(unsigned int target_loose_fragment_no, double &best_similarity)
  {
    unsigned int loose_fragment_counter;
    unsigned int cluster_counter;
    vector<double> similarity_table;
    vector<unsigned int> size_table;
    unsigned int best_cluster;

    // build similarity table of target loose fragment to all clusters
    similarity_table.resize(cluster_id_list.size() + 1);
    size_table.resize(cluster_id_list.size() + 1);
    for(cluster_counter = 1; cluster_counter <= cluster_id_list.size(); ++cluster_counter)
    {
      similarity_table[cluster_counter] = 0.0;
    }
    for(loose_fragment_counter = 0; loose_fragment_counter < loose_fragment_list.size(); ++loose_fragment_counter)
    {
      if(loose_fragment_counter != target_loose_fragment_no)
      {
        double temp_value;

        temp_value = loose_fragment_list[target_loose_fragment_no].GetTotalLFCARSSimilarityToLooseFragment(loose_fragment_list[loose_fragment_counter]);
        // temp_value = loose_fragment_list[target_loose_fragment_no].GetLFCARSSimilarityToLooseFragment(loose_fragment_list[loose_fragment_counter]);
        similarity_table[loose_fragment_clustering_result[loose_fragment_counter]] += temp_value;
        size_table[loose_fragment_clustering_result[loose_fragment_counter]] += loose_fragment_list[loose_fragment_counter].total_size;
      }
    }

    best_cluster = 0;
    best_similarity = (-1.0) * point_number;
    if(LFCARSv100_use_avg_similarity)
    {
      for(cluster_counter = 1; cluster_counter <= cluster_id_list.size(); ++cluster_counter)
      {
        similarity_table[cluster_counter] /= size_table[cluster_counter];
        if(best_similarity < similarity_table[cluster_counter])
        {
          best_similarity = similarity_table[cluster_counter];
          best_cluster = cluster_counter;
        }
      }
    }
    else
    {
      for(cluster_counter = 1; cluster_counter <= cluster_id_list.size(); ++cluster_counter)
      {
        if(best_similarity < similarity_table[cluster_counter])
        {
          best_similarity = similarity_table[cluster_counter];
          best_cluster = cluster_counter;
        }
      }
    }
    return best_cluster;
  }

  bool LFCARSv100::MoveLooseFragmentToCluster(unsigned int loose_fragment_no, unsigned int cluster_no)
  {
    if(loose_fragment_clustering_result[loose_fragment_no] == cluster_no)
    {
      return false;
    }

    if(debug_show_round)
    {
      ofstream output_file;

      output_file.open(debug_show_round_output_filename, ios::app);
      output_file << "LooseFragment " << loose_fragment_no << " : Cluster " << loose_fragment_clustering_result[loose_fragment_no] << " -> Cluster " << cluster_no << endl;
      output_file.close();
    }

    loose_fragment_clustering_result[loose_fragment_no] = cluster_no;

    return true;
  }

  void LFCARSv100::CreateNewClusterForLooseFragment(unsigned int loose_fragment_no)
  {
    set<unsigned int>::iterator cluster_id_iter;
    unsigned int cluster_counter;

    // find a non used cluster number and use it
    for(cluster_counter = 1, cluster_id_iter = cluster_id_list.begin(); cluster_id_iter != cluster_id_list.end() && *cluster_id_iter == cluster_counter; ++cluster_counter, ++cluster_id_iter) ;
    cluster_id_list.insert(cluster_counter);

    if(debug_show_round)
    {
      ofstream output_file;

      output_file.open(debug_show_round_output_filename, ios::app);
      output_file << "LooseFragment " << loose_fragment_no << " : Create New Cluster " << cluster_counter << endl;
      output_file.close();
    }

    MoveLooseFragmentToCluster(loose_fragment_no, cluster_counter);
  }

  void LFCARSv100::SampleFromLooseFragmentsMethod1(vector<unsigned int> &sampling_point_list)
  {
    unsigned int loose_fragment_counter;

    sampling_point_list.clear();
    for(loose_fragment_counter = 0; loose_fragment_counter < loose_fragment_list.size(); ++loose_fragment_counter)
    {
      sampling_point_list.push_back(loose_fragment_list[loose_fragment_counter].core_fragment.point_list[0]);
    }
    sort(sampling_point_list.begin(), sampling_point_list.end());
  }

  void LFCARSv100::SampleFromLooseFragmentsMethod2(vector<unsigned int> &sampling_point_list)
  {
    unsigned int loose_fragment_counter;
    unsigned int random_number;

    sampling_point_list.clear();
    for(loose_fragment_counter = 0; loose_fragment_counter < loose_fragment_list.size(); ++loose_fragment_counter)
    {
      rand_s(&random_number);
      random_number = (unsigned int)((double)random_number / ((double)UINT_MAX + 1.0) * loose_fragment_list[loose_fragment_counter].core_fragment.point_list.size()) + 1;
      sampling_point_list.push_back(loose_fragment_list[loose_fragment_counter].core_fragment.point_list[random_number]);
    }
    sort(sampling_point_list.begin(), sampling_point_list.end());
  }

  void LFCARSv100::TranslateLooseFragmentsToClusteringResult(void)
  {
    unsigned int loose_fragment_counter;
    unsigned int noncore_fragment_counter;
    unsigned int point_counter;

    for(loose_fragment_counter = 0; loose_fragment_counter < loose_fragment_list.size(); ++loose_fragment_counter)
    {
      // core fragment parts
      for(point_counter = 0; point_counter < loose_fragment_list[loose_fragment_counter].core_fragment.point_list.size(); ++point_counter)
      {
        clustering_result[loose_fragment_list[loose_fragment_counter].core_fragment.point_list[point_counter]] = loose_fragment_clustering_result[loose_fragment_counter];
      }

      // noncore fragment parts
      for(noncore_fragment_counter = 0; noncore_fragment_counter < loose_fragment_list[loose_fragment_counter].noncore_fragment_list.size(); ++noncore_fragment_counter)
      {
        for(point_counter = 0; point_counter < loose_fragment_list[loose_fragment_counter].noncore_fragment_list[noncore_fragment_counter].point_list.size(); ++point_counter)
        {
          clustering_result[loose_fragment_list[loose_fragment_counter].noncore_fragment_list[noncore_fragment_counter].point_list[point_counter]] = loose_fragment_clustering_result[loose_fragment_counter];
        }
      }
    }
  }

  FAgglomerative::FAgglomerative(const ConsensusClusteringInformation &consensus_clustering_information)
    : ConsensusClusteringApproach(consensus_clustering_information)
  {
    unsigned int point_counter;
    vector<int> temp_belong_to_cluster_list;
    Fragment temp_fragment;

    point_to_fragment_table.resize(point_number);
    for(point_counter = 0; point_counter < point_number; ++point_counter)
    {
      point_to_fragment_table[point_counter] = 0;  // assign all point to the same Fragment 0
      temp_fragment.point_list.push_back(point_counter);
    }
    fragment_list.push_back(temp_fragment);

    multi_execution_supporting = false;

    debug_show_round = consensus_clustering_information.debug_show_round;
    debug_show_round_output_filename = consensus_clustering_information.output_direction;
    debug_show_round_output_filename += consensus_clustering_information.debug_show_round_output_filename;
    debug_show_fragment_number = consensus_clustering_information.debug_show_fragment_number;
    debug_show_fragment_number_output_filename = consensus_clustering_information.output_direction;
    debug_show_fragment_number_output_filename += consensus_clustering_information.debug_show_fragment_number_output_filename;
  }

  FAgglomerative::~FAgglomerative(void)
  {
  }

  void FAgglomerative::AddOriginalClustering(const vector<int> &input_clustering)
  {
    unsigned int fragment_counter;
    vector<Fragment> temp_fragment_list;
    unsigned int split_fragment_counter;

    timer.PushButton();

    // split the fragments
    for(fragment_counter = 0; fragment_counter < fragment_list.size(); ++fragment_counter)
    {
      vector<Fragment> temp_split_fragment_list = fragment_list[fragment_counter].SplitByClustering(input_clustering);

      for(split_fragment_counter = 0; split_fragment_counter < temp_split_fragment_list.size(); ++split_fragment_counter)
      {
        temp_fragment_list.push_back(temp_split_fragment_list[split_fragment_counter]);
      }
    }
    fragment_list = temp_fragment_list;

    // update original_clustering_number, sum_cluster_number and max_cluster_number
    UpdateClusterNumber(input_clustering);

    timer.PushButton("AddOriginalClustering");
  }

  void FAgglomerative::Initialize(void)
  {
    unsigned int cluster_counter;

    timer.PushButton();

    BuildPointToFragmentTable();
    AllAloneClusteringInitialize(fragment_clustering_result);

    cluster_number = fragment_list.size();

    for(cluster_counter = 0; cluster_counter <= cluster_number; ++cluster_counter)
    {
      vector<unsigned int> temp_cluster_to_fragment_list;

      temp_cluster_to_fragment_list.push_back(cluster_counter - 1); // clusters are from 1 to fragment number, but fragments are from 0 to fragment number - 1
      cluster_to_fragments_list.push_back(temp_cluster_to_fragment_list);
    }

    timer.PushButton("Initial");
  }

  void FAgglomerative::Reset(void)
  {
  }

  void FAgglomerative::Run(void)
  {
    unsigned int iteration_counter = 0;
    bool change_flag = true;
    unsigned int cluster1_counter;
    unsigned int cluster2_counter;
    double temp_distance;
    double min_distance;
    unsigned int min_distance_cluster1;
    unsigned int min_distance_cluster2;
    unsigned int fragment_counter;

    timer.PushButton();

    if(debug_show_round)
    {
      unsigned int fragment_counter;
      ofstream output_file;

      output_file.open(debug_show_round_output_filename, ios::out);
      for(fragment_counter = 0; fragment_counter <= fragment_clustering_result.size(); ++fragment_counter)
      {
        output_file << fragment_clustering_result[fragment_counter] << " ";
      }
      output_file << endl;
      output_file.close();
    }

    for(++iteration_counter; change_flag; ++iteration_counter)
    {
      change_flag = false;
      min_distance = -1.0;
      min_distance_cluster1 = min_distance_cluster2 = 0;

      for(cluster1_counter = 1; cluster1_counter <= cluster_number; ++cluster1_counter)
      {
        if(cluster_to_fragments_list[cluster1_counter].size() > 0)
        {
          for(cluster2_counter = cluster1_counter + 1; cluster2_counter <= cluster_number; ++cluster2_counter)
          {
            if(cluster_to_fragments_list[cluster2_counter].size() > 0)
            {
              temp_distance = CalculateDistanceBetweenClusters(cluster1_counter, cluster2_counter);

              if(min_distance < 0.0 || (min_distance >= 0.0 && min_distance > temp_distance))
              {
                min_distance = temp_distance;
                min_distance_cluster1 = cluster1_counter;
                min_distance_cluster2 = cluster2_counter;

                if(debug_show_round)
                {
                  ofstream output_file;

                  output_file.open(debug_show_round_output_filename, ios::app);
                  output_file.precision(6);
                  output_file << "Round " << iteration_counter << " Min Distance Change : Cluster " << min_distance_cluster1 << ", Cluster " << min_distance_cluster2 << " = " << min_distance << endl;
                  output_file.close();
                }
              }
            }
          }
        }
      }

      if(debug_show_round)
      {
        ofstream output_file;

        output_file.open(debug_show_round_output_filename, ios::app);
        output_file.precision(6);
        output_file << "Round " << iteration_counter << " Min Distance : Cluster " << min_distance_cluster1 << ", Cluster " << min_distance_cluster2 << " = " << min_distance << endl;
        output_file.close();
      }

      if(min_distance >= 0.0 && min_distance < 0.5)
      {
        for(fragment_counter = 0; fragment_counter < fragment_clustering_result.size(); ++fragment_counter)
        {
          if(fragment_clustering_result[fragment_counter] == min_distance_cluster2)
          {
            fragment_clustering_result[fragment_counter] = min_distance_cluster1;
          }
        }
        
        if(debug_show_round)
        {
          ofstream output_file;

          output_file.open(debug_show_round_output_filename, ios::app);
          for(fragment_counter = 0; fragment_counter < cluster_to_fragments_list[min_distance_cluster1].size(); ++fragment_counter)
          {
            output_file << cluster_to_fragments_list[min_distance_cluster1][fragment_counter] << " ";
          }
          output_file << "<- ";
          for(fragment_counter = 0; fragment_counter < cluster_to_fragments_list[min_distance_cluster2].size(); ++fragment_counter)
          {
            output_file << cluster_to_fragments_list[min_distance_cluster2][fragment_counter] << " ";
          }
          output_file << endl;
          output_file.close();
        }

        for(fragment_counter = 0; fragment_counter < cluster_to_fragments_list[min_distance_cluster2].size(); ++fragment_counter)
        {
          cluster_to_fragments_list[min_distance_cluster1].push_back(cluster_to_fragments_list[min_distance_cluster2][fragment_counter]);
        }
        cluster_to_fragments_list[min_distance_cluster2].clear();

        if(debug_show_round)
        {
          ofstream output_file;

          output_file.open(debug_show_round_output_filename, ios::app);
          for(fragment_counter = 0; fragment_counter < cluster_to_fragments_list[min_distance_cluster1].size(); ++fragment_counter)
          {
            output_file << cluster_to_fragments_list[min_distance_cluster1][fragment_counter] << " ";
          }
          output_file << endl;
          output_file.close();
        }

        change_flag = true;
      }

      if(debug_show_round)
      {
        unsigned int fragment_counter;
        ofstream output_file;

        output_file.open(debug_show_round_output_filename, ios::app);
        for(fragment_counter = 0; fragment_counter < fragment_clustering_result.size(); ++fragment_counter)
        {
          output_file << fragment_clustering_result[fragment_counter] << " ";
        }
        output_file << endl;
        output_file.close();
      }
    }

    TranslateFragmentsToClusteringResult();

    timer.PushButton("Run");
  }

  void FAgglomerative::BuildPointToFragmentTable(void)
  {
    unsigned int fragment_counter;
    unsigned int point_counter;
    double avg_fragment_size = 0.0;
    double std_fragment_size = 0.0;

    // sort(fragment_list.begin(), fragment_list.end(), FragmentNoCompare);

    for(fragment_counter = 0; fragment_counter < fragment_list.size(); ++fragment_counter)
    {
      for(point_counter = 0; point_counter < fragment_list[fragment_counter].point_list.size(); ++point_counter)
      {
        point_to_fragment_table[fragment_list[fragment_counter].point_list[point_counter]] = fragment_counter;
      }

      if(debug_show_fragment_number)
      {
        avg_fragment_size += fragment_list[fragment_counter].point_list.size();
        std_fragment_size += (double)(fragment_list[fragment_counter].point_list.size() * fragment_list[fragment_counter].point_list.size());
      }
    }

    fragment_clustering_result.resize(fragment_list.size());

    if(debug_show_fragment_number)
    {
      ofstream output_file;

      avg_fragment_size /= fragment_list.size();
      std_fragment_size = sqrt(std_fragment_size / fragment_list.size() - avg_fragment_size * avg_fragment_size);
      
      output_file.open(debug_show_fragment_number_output_filename, ios::out);

      for(point_counter = 0; point_counter < clustering_result.size(); ++point_counter)
      {
        output_file << point_to_fragment_table[point_counter] << " ";
      }
      output_file << endl;

      output_file << "Fragment Number      = " << fragment_list.size() << endl;
      output_file << "Avg Fragment Size    = " << avg_fragment_size << endl;
      output_file << "Std of Fragment Size = " << std_fragment_size << endl;

      output_file.close();
    }

  }

  double FAgglomerative::CalculateDistanceBetweenClusters(unsigned int cluster1, unsigned int cluster2)
  {
    unsigned int fragment1_counter;
    unsigned int fragment2_counter;
    double distance_sum = 0.0;
    unsigned int cluster1_size = 0;
    unsigned int cluster2_size = 0;

    for(fragment1_counter = 0; fragment1_counter < cluster_to_fragments_list[cluster1].size(); ++fragment1_counter)
    {
      cluster1_size += fragment_list[cluster_to_fragments_list[cluster1][fragment1_counter]].point_list.size();
    }

    for(fragment2_counter = 0; fragment2_counter < cluster_to_fragments_list[cluster2].size(); ++fragment2_counter)
    {
      cluster2_size += fragment_list[cluster_to_fragments_list[cluster2][fragment2_counter]].point_list.size();
    }

    for(fragment1_counter = 0; fragment1_counter < cluster_to_fragments_list[cluster1].size(); ++fragment1_counter)
    {
      for(fragment2_counter = 0; fragment2_counter < cluster_to_fragments_list[cluster2].size(); ++fragment2_counter)
      {
        distance_sum += fragment_list[cluster_to_fragments_list[cluster1][fragment1_counter]].GetNormalDistanceToFragment(fragment_list[cluster_to_fragments_list[cluster2][fragment2_counter]])
          * fragment_list[cluster_to_fragments_list[cluster1][fragment1_counter]].point_list.size()
          * fragment_list[cluster_to_fragments_list[cluster2][fragment2_counter]].point_list.size();
      }
    }

    return distance_sum / cluster1_size / cluster2_size;
  }

  void FAgglomerative::TranslateFragmentsToClusteringResult(void)
  {
    unsigned int fragment_counter;
    unsigned int point_counter;

    for(fragment_counter = 0; fragment_counter < fragment_list.size(); ++fragment_counter)
    {
      for(point_counter = 0; point_counter < fragment_list[fragment_counter].point_list.size(); ++point_counter)
      {
        clustering_result[fragment_list[fragment_counter].point_list[point_counter]] = fragment_clustering_result[fragment_counter];
      }
    }
  }

  bool FAgglomerative::FragmentNoCompare(const Fragment &fragment1, const Fragment &fragment2)
  {
    return fragment1.point_list[0] < fragment2.point_list[0];
  }

  SimilarityMatrix::SimilarityMatrix(void)
  {
    number_of_clustering = 0;
    similarity_matrix.clear();
  }

  SimilarityMatrix::SimilarityMatrix(unsigned int n_of_vertices)
  {
    Initialize(n_of_vertices);
  }

  SimilarityMatrix::~SimilarityMatrix()
  {
    similarity_matrix.clear();
  }

  void SimilarityMatrix::Initialize(unsigned int n_of_vertices)
  {
    unsigned int size_counter;
    
    for(size_counter = 0; size_counter < n_of_vertices; ++size_counter)
    {
      vector<int> temp_vector;

      temp_vector.resize(n_of_vertices);
      similarity_matrix.push_back(temp_vector);
    }
  }

  void SimilarityMatrix::Reset(void)
  {
    number_of_clustering = 0;
    similarity_matrix.clear();
  }

  bool SimilarityMatrix::AddOriginalClustering(const vector<int> &input_clustering)
  {
    unsigned int point_counter_1, point_counter_2;

    ++number_of_clustering;
    for(point_counter_1 = 0; point_counter_1 < input_clustering.size(); ++point_counter_1)
    {
      similarity_matrix[point_counter_1][point_counter_1] += 1;
      for(point_counter_2 = point_counter_1 + 1; point_counter_2 < input_clustering.size(); ++point_counter_2)
      {
        if(input_clustering[point_counter_1] != kUnclassifiedPoint &&
          input_clustering[point_counter_2] != kUnclassifiedPoint &&
          input_clustering[point_counter_1] != kNoisePoint &&
          input_clustering[point_counter_2] != kNoisePoint &&
          input_clustering[point_counter_1] == input_clustering[point_counter_2])
        {
          similarity_matrix[point_counter_1][point_counter_2] += 1;
          similarity_matrix[point_counter_2][point_counter_1] += 1;
        }
      }
    }

    return(true);
  }

  unsigned int SimilarityMatrix::GetNumberOfClustering(void)
  {
    return number_of_clustering;
  }

  void SimilarityMatrix::TransformToCSPAFormat(idx_t *&xadj, idx_t *&adjncy, idx_t *&vwgt, idx_t *&vsize, idx_t *&adjwgt)
  {
    unsigned int point_counter_1, point_counter_2;
    unsigned int number_of_edge = 0;
    unsigned int adj_counter;
    unsigned int edge_counter;
    vector<idx_t> adj_list;
    vector<idx_t> edge_list;
    vector<idx_t> weight_list;

    adj_list.push_back(number_of_edge);
    for(point_counter_1 = 0; point_counter_1 < similarity_matrix.size(); ++point_counter_1)
    {
      for(point_counter_2 = 0; point_counter_2 < similarity_matrix.size(); ++point_counter_2)
      {
        if(point_counter_1 != point_counter_2 &&
          similarity_matrix[point_counter_1][point_counter_2] > 0.0)
        {
          ++number_of_edge;
          edge_list.push_back(point_counter_2);
          weight_list.push_back(similarity_matrix[point_counter_1][point_counter_2]);
        }
      }
      adj_list.push_back(number_of_edge);
    }
    
    xadj = new idx_t[similarity_matrix.size() + 1];
    adjncy = new idx_t[number_of_edge];
    vwgt = NULL;
    vsize = NULL;
    adjwgt = new idx_t[number_of_edge];
    
    for(adj_counter = 0; adj_counter < adj_list.size(); ++adj_counter)
    {
      xadj[adj_counter] = adj_list[adj_counter];
    }
    for(edge_counter = 0; edge_counter < edge_list.size(); ++edge_counter)
    {
      adjncy[edge_counter] = edge_list[edge_counter];
      adjwgt[edge_counter] = weight_list[edge_counter];
    }
  }

  CSPA::CSPA(const ConsensusClusteringInformation &consensus_clustering_information)
    : ConsensusClusteringApproach(consensus_clustering_information)
  {
    cluster_number_choosing_method = consensus_clustering_information.cluster_number_choosing_method;
    cluster_number_multiple = consensus_clustering_information.cluster_number_multiple;

    sum_cluster_number = 0;

    similarity_matrix.Initialize(point_number); 

    multi_execution_supporting = false;
  }

  CSPA::~CSPA(void)
  {
  }

  void CSPA::AddOriginalClustering(const vector<int> &input_clustering)
  {
    unsigned int input_clustering_number = GetClusterNumber(input_clustering);

    timer.PushButton();

    similarity_matrix.AddOriginalClustering(input_clustering);

    // update original_clustering_number, sum_cluster_number and max_cluster_number
    UpdateClusterNumber(input_clustering);

    timer.PushButton("AddOriginalClustering");
  }

  void CSPA::Initialize(void)
  {
    timer.Reset();

    timer.PushButton("Initial");
  }

  void CSPA::Reset(void)
  {
    timer.Reset();

    timer.PushButton("Initial");
  }

  void CSPA::Run(void)
  {
    idx_t nvtxs, ncon;
    idx_t *xadj, *adjncy, *vwgt, *vsize, *adjwgt;
    idx_t nparts;
    real_t *tpwgts, *ubvec;
    idx_t *options;
    idx_t objval;
    idx_t *part;

    unsigned int point_counter;

    timer.Reset();

    nvtxs = point_number;
    ncon = 1;
    xadj = NULL;
    adjncy = NULL;
    vwgt = NULL;
    vsize = NULL;
    adjwgt = NULL;
    similarity_matrix.TransformToCSPAFormat(xadj, adjncy, vwgt, vsize, adjwgt);
    if(cluster_number_choosing_method == "Given")
    {
      nparts = cluster_number;
    }
    else if(cluster_number_choosing_method == "AvgK")
    {
      nparts = (idx_t)ceil((double)sum_cluster_number / original_clustering_number);
    }
    else if(cluster_number_choosing_method == "MaxK")
    {
      nparts = max_cluster_number;
    }
    else
    {
      nparts = cluster_number;
    }
    tpwgts = NULL;
    ubvec = NULL;
    options = NULL;
    objval = 0;
    part = (idx_t *)malloc(sizeof(idx_t) * nvtxs);

    METIS_PartGraphRecursive(&nvtxs, &ncon, xadj, adjncy, vwgt, vsize, adjwgt, &nparts, tpwgts, ubvec, options, &objval, part);

    for(point_counter = 0; point_counter < point_number; ++point_counter)
    {
      clustering_result[point_counter] = part[point_counter] + 1;
    }

    delete [] xadj;
    delete [] adjncy;
    delete [] adjwgt;
    free(part);

    timer.PushButton("Run");
  }

  Hypergraph::Hypergraph(void)
  {
    number_of_vertices = 0;
    number_of_clustering = 0;
    hyperedges.clear();
  }

  Hypergraph::Hypergraph(unsigned int n_of_vertices)
  {
    Initialize(n_of_vertices);
  }

  Hypergraph::~Hypergraph()
  {
    hyperedges.clear();
  }

  void Hypergraph::Initialize(unsigned int n_of_vertices)
  {
    number_of_vertices = n_of_vertices;
  }

  void Hypergraph::Reset(void)
  {
    number_of_vertices = 0;
    number_of_clustering = 0;
    hyperedges.clear();
  }

  bool Hypergraph::AddOriginalClustering(const vector<int> &input_clustering)
  {
    unsigned int point_counter, hyperedge_counter;

    ++number_of_clustering;
    for(point_counter = 0; point_counter < input_clustering.size(); ++point_counter)
    {
      if(input_clustering[point_counter] != kUnclassifiedPoint &&
        input_clustering[point_counter] != kNoisePoint)
      {
        for(hyperedge_counter = 0; hyperedge_counter < hyperedges.size(); ++hyperedge_counter)
        {
          if(input_clustering[point_counter] == input_clustering[hyperedges[hyperedge_counter][0]])
          {
            hyperedges[hyperedge_counter].push_back(point_counter);
            break;
          }
        }
        if(hyperedge_counter == hyperedges.size())
        {
          vector<unsigned int> new_hyperedge;

          new_hyperedge.push_back(point_counter);
          hyperedges.push_back(new_hyperedge);
        }
      }
      else if(input_clustering[point_counter] == kNoisePoint)
      {
        vector<unsigned int> new_hyperedge;

        new_hyperedge.push_back(point_counter);
        hyperedges.push_back(new_hyperedge);
      }
      else if(input_clustering[point_counter] == kUnclassifiedPoint)
      {
      }
    }

    return(true);
  }

  unsigned int Hypergraph::GetNumberOfClustering(void)
  {
    return number_of_clustering;
  }

  unsigned int Hypergraph::GetNumberOfHyperedges(void)
  {
    return hyperedges.size();
  }

  void Hypergraph::TransformToHMETISFormat(int &nhedges, int *&eptr, int *&eind)
  {
    unsigned int hyperedge_counter, point_counter;
    unsigned int eptr_counter;
    unsigned int eind_counter;
    vector<int> eptr_list;
    vector<int> eind_list;

    eind_counter = 0;
    eptr_list.push_back(eind_counter);
    for(hyperedge_counter = 0; hyperedge_counter < hyperedges.size(); ++hyperedge_counter)
    {
      for(point_counter = 0; point_counter < hyperedges[hyperedge_counter].size(); ++point_counter)
      {
        eind_list.push_back(hyperedges[hyperedge_counter][point_counter]);
      }
      eind_counter += hyperedges[hyperedge_counter].size();
      eptr_list.push_back(eind_counter);
    }
   
    eptr = (int *)malloc(sizeof(int) * eptr_list.size());
    eind = (int *)malloc(sizeof(int) * eind_list.size());

    for(eptr_counter = 0; eptr_counter < eptr_list.size(); ++eptr_counter)
    {
      eptr[eptr_counter] = eptr_list[eptr_counter];
    }
    for(eind_counter = 0; eind_counter < eind_list.size(); ++eind_counter)
    {
      eind[eind_counter] = eind_list[eind_counter];
    }
  }

  void Hypergraph::TransformToMCLAFormat(idx_t *&xadj, idx_t *&adjncy, idx_t *&vwgt, idx_t *&vsize, idx_t *&adjwgt)
  {
    unsigned int hyperedge_counter_1, hyperedge_counter_2;
    unsigned int number_of_edge = 0;
    unsigned int adj_counter;
    unsigned int edge_counter;
    double temp_weight;
    vector<idx_t> adj_list;
    vector<idx_t> edge_list;
    vector<idx_t> weight_list;

    adj_list.push_back(number_of_edge);
    for(hyperedge_counter_1 = 0; hyperedge_counter_1 < hyperedges.size(); ++hyperedge_counter_1)
    {
      for(hyperedge_counter_2 = 0; hyperedge_counter_2 < hyperedges.size(); ++hyperedge_counter_2)
      {
        if(hyperedge_counter_1 != hyperedge_counter_2)
        {
          temp_weight = BinaryJaccardSimilarity(hyperedge_counter_1, hyperedge_counter_2);
          if(temp_weight > 0.0)
          {
            ++number_of_edge;
            edge_list.push_back(hyperedge_counter_2);
            weight_list.push_back((idx_t)(temp_weight * number_of_vertices));
          }
        }
      }
      adj_list.push_back(number_of_edge);
    }
    
    xadj = new idx_t[hyperedges.size() + 1];
    adjncy = new idx_t[number_of_edge];
    vwgt = NULL;
    vsize = NULL;
    adjwgt = new idx_t[number_of_edge];
    
    for(adj_counter = 0; adj_counter < adj_list.size(); ++adj_counter)
    {
      xadj[adj_counter] = adj_list[adj_counter];
    }
    for(edge_counter = 0; edge_counter < edge_list.size(); ++edge_counter)
    {
      adjncy[edge_counter] = edge_list[edge_counter];
      adjwgt[edge_counter] = weight_list[edge_counter];
    }
  }

  void Hypergraph::CollapseHyperedges(unsigned int point_number, idx_t nvtxs, idx_t *part, vector<vector<double>> &meta_hypergraph)
  {
    int hyperedge_counter;
    unsigned int point_counter;
    unsigned int meta_hyperedge_point_counter;
    unsigned int meta_hyperedge_counter;
    vector<int> meta_hyperedge_no_table;
    vector<unsigned int> meta_hyperedge_count_table;

    meta_hypergraph.clear();
    
    for(hyperedge_counter = 0; hyperedge_counter < nvtxs; ++hyperedge_counter)
    {
      for(meta_hyperedge_counter = 0; meta_hyperedge_counter < meta_hyperedge_no_table.size(); ++meta_hyperedge_counter)
      {
        if(part[hyperedge_counter] == meta_hyperedge_no_table[meta_hyperedge_counter])
        {
          break;
        }
      }
      if(meta_hyperedge_counter == meta_hyperedge_no_table.size())
      {
        vector<double> temp_meta_hyperedge;

        meta_hyperedge_no_table.push_back(part[hyperedge_counter]);
        meta_hyperedge_count_table.push_back(0);
        temp_meta_hyperedge.resize(number_of_vertices);
        meta_hypergraph.push_back(temp_meta_hyperedge);
      }

      ++meta_hyperedge_count_table[meta_hyperedge_counter];
      for(point_counter = 0; point_counter < hyperedges[hyperedge_counter].size(); ++point_counter)
      {
        meta_hypergraph[meta_hyperedge_counter][hyperedges[hyperedge_counter][point_counter]] += 1.0;
      }
    }

    for(meta_hyperedge_counter = 0; meta_hyperedge_counter < meta_hyperedge_no_table.size(); ++meta_hyperedge_counter)
    {
      for(meta_hyperedge_point_counter = 0; meta_hyperedge_point_counter < point_number; ++meta_hyperedge_point_counter)
      {
        meta_hypergraph[meta_hyperedge_counter][meta_hyperedge_point_counter] /= meta_hyperedge_count_table[meta_hyperedge_counter];
      }
    }
  }

  double Hypergraph::BinaryJaccardSimilarity(unsigned int edge1, unsigned int edge2)
  {
    return Dot(edge1, edge2) / (Dot(edge1, edge1) + Dot(edge2, edge2) - Dot(edge1, edge2));
  }

  double Hypergraph::Dot(unsigned int edge1, unsigned int edge2)
  {
    unsigned int list_counter1, list_counter2;
    unsigned int value = 0;

    if(edge1 == edge2)
    {
      value = hyperedges[edge1].size();
    }
    else
    {
      for(list_counter1 = 0, list_counter2 = 0;
        list_counter1 < hyperedges[edge1].size() && list_counter2 < hyperedges[edge2].size(); )
      {
        if(hyperedges[edge1][list_counter1] == hyperedges[edge2][list_counter2])
        {
          ++value;
          ++list_counter1;
          ++list_counter2;
        }
        else if(hyperedges[edge1][list_counter1] > hyperedges[edge2][list_counter2])
        {
          ++list_counter2;
        }
        else if(hyperedges[edge1][list_counter1] < hyperedges[edge2][list_counter2])
        {
          ++list_counter1;
        }
      }
    }

    return (double)value;
  }

/*
  HGPA::HGPA(const ConsensusClusteringInformation &consensus_clustering_information)
    : ConsensusClusteringApproach(consensus_clustering_information)
  {
    cluster_number_choosing_method = consensus_clustering_information.cluster_number_choosing_method;
    cluster_number_multiple = consensus_clustering_information.cluster_number_multiple;

    sum_cluster_number = 0;

    hypergraph.Initialize(point_number); 

    multi_execution_supporting = false;
  }

  HGPA::~HGPA(void)
  {
  }

  void HGPA::AddOriginalClustering(const vector<int> &input_clustering)
  {
    unsigned int input_clustering_number = GetClusterNumber(input_clustering);

    timer.PushButton();

    hypergraph.AddOriginalClustering(input_clustering);

    // update original_clustering_number
    UpdateOriginalClusteringNumber();

    // update sum_cluster_number
    sum_cluster_number += input_clustering_number;

    // update max_cluster_number
    if(max_cluster_number < input_clustering_number)
    {
      max_cluster_number = input_clustering_number;
    }

    timer.PushButton("AddOriginalClustering");
  }

  void HGPA::Initialize(void)
  {
    timer.Reset();

    timer.PushButton("Initial");
  }

  void HGPA::Reset(void)
  {
    timer.Reset();

    timer.PushButton("Initial");
  }

  void HGPA::Run(void)
  {
    int nvtxs, nhedges;
    int *vwgts;
    int *eptr, *eind;
    int *hewgts;
    int nparts;
    int ubfactor;
    int *options;
    int *part;
//    int edgecut;

    unsigned int point_counter;

    timer.Reset();

    options = (int *)malloc(sizeof(int) * 9);

    nvtxs = point_number;
    vwgts = NULL;
    hypergraph.TransformToHMETISFormat(nhedges, eptr, eind);
    hewgts = NULL;
    if(cluster_number_choosing_method == "Given")
    {
      nparts = cluster_number;
    }
    else if(cluster_number_choosing_method == "AvgK")
    {
      nparts = (idx_t)ceil((double)sum_cluster_number / hypergraph.GetNumberOfClustering());
    }
    else if(cluster_number_choosing_method == "MaxK")
    {
      nparts = max_cluster_number;
    }
    else
    {
      nparts = cluster_number;
    }
    ubfactor = 5;
    options[0] = 0; // used default values
    part = (int *)malloc(sizeof(int) * nvtxs);

//    HMETIS_PartRecursive(nvtxs, nhedges, vwgts, eptr, eind, hewgts, nparts, ubfactor, options, part, &edgecut);

    for(point_counter = 0; point_counter < point_number; ++point_counter)
    {
      clustering_result[point_counter] = part[point_counter] + 1;
    }

    delete [] eptr;
    delete [] eind;
    delete [] options;
    delete [] part;

    timer.PushButton("Run");
  }
*/

  MCLA::MCLA(const ConsensusClusteringInformation &consensus_clustering_information)
    : ConsensusClusteringApproach(consensus_clustering_information)
  {
    cluster_number_choosing_method = consensus_clustering_information.cluster_number_choosing_method;
    cluster_number_multiple = consensus_clustering_information.cluster_number_multiple;

    sum_cluster_number = 0;

    hypergraph.Initialize(point_number); 

    multi_execution_supporting = false;
  }

  MCLA::~MCLA(void)
  {
  }

  void MCLA::AddOriginalClustering(const vector<int> &input_clustering)
  {
    unsigned int input_clustering_number = GetClusterNumber(input_clustering);

    timer.PushButton();

    // MCLA Step 1: Construct Meta-graph
    hypergraph.AddOriginalClustering(input_clustering);

    // update original_clustering_number, sum_cluster_number and max_cluster_number
    UpdateClusterNumber(input_clustering);

    timer.PushButton("AddOriginalClustering");
  }

  void MCLA::Initialize(void)
  {
    timer.Reset();

    timer.PushButton("Initial");
  }

  void MCLA::Reset(void)
  {
    timer.Reset();

    timer.PushButton("Initial");
  }

  void MCLA::Run(void)
  {
    idx_t nvtxs, ncon;
    idx_t *xadj, *adjncy, *vwgt, *vsize, *adjwgt;
    idx_t nparts;
    real_t *tpwgts, *ubvec;
    idx_t *options;
    idx_t objval;
    idx_t *part;
    vector<vector<double>> meta_hypergraph;
    unsigned int point_counter;
    unsigned int meta_hyperedge_counter;
    unsigned int max_meta_cluster;
    double max_value;

    timer.Reset();

    // MCLA Step 1: Construct Meta-graph
    nvtxs = hypergraph.GetNumberOfHyperedges();
    ncon = 1;
    xadj = NULL;
    adjncy = NULL;
    vwgt = NULL;
    vsize = NULL;
    adjwgt = NULL;
    hypergraph.TransformToMCLAFormat(xadj, adjncy, vwgt, vsize, adjwgt);
    if(cluster_number_choosing_method == "Given")
    {
      nparts = cluster_number;
    }
    else if(cluster_number_choosing_method == "AvgK")
    {
      nparts = (idx_t)ceil((double)sum_cluster_number / original_clustering_number);
    }
    else if(cluster_number_choosing_method == "MaxK")
    {
      nparts = max_cluster_number;
    }
    else
    {
      nparts = cluster_number;
    }
    tpwgts = NULL;
    ubvec = NULL;
    options = NULL;
    objval = 0;
    part = (idx_t *)malloc(sizeof(idx_t) * nvtxs);

    // MCLA Step 2: Cluster Hyperedges
    METIS_PartGraphRecursive(&nvtxs, &ncon, xadj, adjncy, vwgt, vsize, adjwgt, &nparts, tpwgts, ubvec, options, &objval, part);

    // MCLA Step 3: Collapse Meta-clusters
    hypergraph.CollapseHyperedges(point_number, nvtxs, part, meta_hypergraph);

    // MCLA Step 4: Compete for Objects
    for(point_counter = 0; point_counter < point_number; ++point_counter)
    {
      max_meta_cluster = -1;
      max_value = -1.0;
      for(meta_hyperedge_counter = 0; meta_hyperedge_counter < meta_hypergraph.size(); ++meta_hyperedge_counter)
      {
        if(max_value < meta_hypergraph[meta_hyperedge_counter][point_counter])
        {
          max_meta_cluster = meta_hyperedge_counter;
          max_value = meta_hypergraph[meta_hyperedge_counter][point_counter];
        }
      }
      clustering_result[point_counter] = max_meta_cluster + 1;
    }

    delete [] xadj;
    delete [] adjncy;
    delete [] adjwgt;
    free(part);

    timer.PushButton("Run");
  }
}
